#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution 
{
    int recursion(TreeNode * node, int depth)
    {
        if(node->left == nullptr && node->right ==nullptr)
        {
            return depth;
        }
        if(node->left == nullptr && node->right != nullptr)
        {
            return recursion(node->right, depth + 1);
        }
        if(node->left != nullptr && node->right == nullptr)
        {
            return recursion(node->left, depth + 1);
        }
        return min(recursion(node->left, depth + 1), recursion(node->right, depth + 1));
    }
public:
    int minDepth(TreeNode* root) 
    {
        if(root == nullptr)
        {
            return 0;
        }
        return recursion(root, 1);
    }
};

// 辅助函数：创建二叉树节点
TreeNode* createNode(int val) {
    return new TreeNode(val);
}

// 辅助函数：释放二叉树内存
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    Solution solution;
    
    cout << "=== LeetCode 111. 二叉树的最小深度 测试案例 ===" << endl;
    
    // 测试案例1: 示例1 - [3,9,20,null,null,15,7]
    cout << "\n测试案例1: [3,9,20,null,null,15,7]" << endl;
    TreeNode* root1 = createNode(3);
    root1->left = createNode(9);
    root1->right = createNode(20);
    root1->right->left = createNode(15);
    root1->right->right = createNode(7);
    
    int result1 = solution.minDepth(root1);
    cout << "输入: [3,9,20,null,null,15,7]" << endl;
    cout << "输出: " << result1 << endl;
    cout << "期望: 2" << endl;
    
    // 测试案例2: 示例2 - [2,null,3,null,4,null,5,null,6]
    cout << "\n测试案例2: [2,null,3,null,4,null,5,null,6]" << endl;
    TreeNode* root2 = createNode(2);
    root2->right = createNode(3);
    root2->right->right = createNode(4);
    root2->right->right->right = createNode(5);
    root2->right->right->right->right = createNode(6);
    
    int result2 = solution.minDepth(root2);
    cout << "输入: [2,null,3,null,4,null,5,null,6]" << endl;
    cout << "输出: " << result2 << endl;
    cout << "期望: 5" << endl;
    
    // 测试案例3: 只有一个节点
    cout << "\n测试案例3: 只有一个节点 [1]" << endl;
    TreeNode* root3 = createNode(1);
    
    int result3 = solution.minDepth(root3);
    cout << "输入: [1]" << endl;
    cout << "输出: " << result3 << endl;
    cout << "期望: 1" << endl;
    
    // 测试案例4: 空树
    cout << "\n测试案例4: 空树 []" << endl;
    TreeNode* root4 = nullptr;
    
    int result4 = solution.minDepth(root4);
    cout << "输入: []" << endl;
    cout << "输出: " << result4 << endl;
    cout << "期望: 0" << endl;
    
    // 测试案例5: 只有左子树 [1,2,null,3]
    cout << "\n测试案例5: 只有左子树 [1,2,null,3]" << endl;
    TreeNode* root5 = createNode(1);
    root5->left = createNode(2);
    root5->left->left = createNode(3);
    
    int result5 = solution.minDepth(root5);
    cout << "输入: [1,2,null,3]" << endl;
    cout << "输出: " << result5 << endl;
    cout << "期望: 3" << endl;
    
    // 测试案例6: 完全二叉树 [1,2,3,4,5]
    cout << "\n测试案例6: 完全二叉树 [1,2,3,4,5]" << endl;
    TreeNode* root6 = createNode(1);
    root6->left = createNode(2);
    root6->right = createNode(3);
    root6->left->left = createNode(4);
    root6->left->right = createNode(5);
    
    int result6 = solution.minDepth(root6);
    cout << "输入: [1,2,3,4,5]" << endl;
    cout << "输出: " << result6 << endl;
    cout << "期望: 2" << endl;
    
    // 释放内存
    deleteTree(root1);
    deleteTree(root2);
    deleteTree(root3);
    // root4 已经是 nullptr，不需要释放
    deleteTree(root5);
    deleteTree(root6);
    
    cout << "\n=== 测试完成 ===" << endl;
    
    return 0;
}